/// https://www.rustfinity.com/practice/rust/challenges/maze-solver
use std::collections::{BTreeMap, VecDeque};
type Loc = (usize, usize);
type MazeRep = Vec<Vec<char>>;
type Maze = Vec<Vec<Tile>>;
#[derive(Debug, PartialEq, Eq)]
enum Tile {
    Empty,
    Wall,
}
#[derive(Debug)]
enum MazeError {
    FormatError,
}
impl std::fmt::Display for MazeError {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "maze format error")
    }
}
impl std::error::Error for MazeError {}
fn clean_maze(
    maze: MazeRep,
    start: Loc,
    end: Loc,
) -> Result<Vec<Vec<Tile>>, MazeError> {
    let mut found_start = false;
    let mut found_end = false;
    let result: Vec<Vec<Tile>> = maze.into_iter().enumerate().map(|(r, row)| {
        row.into_iter().enumerate().map(|(c, square)| {
            match square {
                '#' => Ok(Tile::Wall),
                '.' => Ok(Tile::Empty),
                'S' if (r, c) == start => {
                    found_start = true;
                    Ok(Tile::Empty)
                }
                'E' if (r, c) == end => {
                    found_end = true;
                    Ok(Tile::Empty)
                }
                _ => Err(MazeError::FormatError)
            }
        }).collect::<Result<Vec<Tile>, MazeError>>()
    }).collect::<Result<Vec<Vec<Tile>>, MazeError>>()?;
    if !found_start || !found_end {
        return Err(MazeError::FormatError);
    }
    Ok(result)
}
const ADJ: [(isize, isize); 4] = [
    (0, -1),
    (0, 1),
    (-1, 0),
    (1, 0),
];
fn neighbors(maze: &Maze, (r0, c0): Loc) -> impl Iterator<Item=Loc> {
    let mut locs = Vec::new();
    for (dr, dc) in ADJ {
        let (r, c) = (r0 as isize + dr, c0 as isize + dc);
        if r >= 0 && (r as usize) < maze.len()
            && c >= 0 && (c as usize) < maze[r as usize].len()
            && maze[r as usize][c as usize] == Tile::Empty
        {
            locs.push((r as usize, c as usize));
        }
    }
    locs.into_iter()
}
fn search(
    maze: &Maze,
    start: Loc,
    end: Loc,
) -> Option<BTreeMap<Loc, Option<Loc>>> {
    let mut stop = BTreeMap::new();
    let mut q = VecDeque::new();
    q.push_back(start);
    stop.insert(start, None);
    while let Some(cur) = q.pop_front() {
        if cur == end {
            return Some(stop);
        }
        for n in neighbors(maze, cur) {
            stop.entry(n).or_insert_with(|| {
                q.push_back(n);
                Some(cur)
            });
        }
    }
    None
}
pub fn solve_maze(
    maze: MazeRep,
    start: Loc,
    end: Loc,    
) -> Vec<Loc> {
    let maze = clean_maze(maze, start, end).unwrap();
    match search(&maze, start, end) {
        Some(soln) => {
            let mut result = Vec::new();
            let mut cur = Some(end);
            while let Some(next) = cur {
                result.push(next);
                cur = *soln.get(&next).unwrap();
            }
            result.reverse();
            result
        }
        None => Vec::new(),
    }
}
#[test]
fn test_solve_maze() {
    let maze = vec![
        vec!['S', '.', '#', '#', '#'],
        vec!['#', '.', '#', '.', '.'],
        vec!['#', '.', '.', '.', '#'],
        vec!['#', '#', '#', '.', '#'],
        vec!['#', '#', '#', 'E', '#']
    ];
    let start = (0, 0);
    let end = (4, 3);
    let path = solve_maze(maze, start, end);
    assert_eq!(
        path,
        vec![
            (0, 0), // starting point
            (0, 1), // right
            (1, 1), // down
            (2, 1), // down
            (2, 2), // right
            (2, 3), // right
            (3, 3), // down
            (4, 3) // down
        ]
    );
}
2.80ms